---
title: STL 容器
---

C++ 標準模板庫 (STL) 提供了一組豐富的通用類別和函式，它們實作了常見的資料結構和演算法。**容器**是儲存資料的物件。它們是模板類別，這表示它們可以容納任何資料類型的元素。理解 STL 容器對於高效且穩健的 C++ 程式設計至關重要，它提供了 JavaScript 內建陣列和物件類型的一個強大替代方案。

## 序列容器：`vector`、`list`、`deque`

序列容器以線性方式儲存元素，允許透過其位置存取元素。

### `std::vector`

*   **動態陣列：** 類似於 JavaScript 陣列，`std::vector` 是一個動態陣列，其大小可以增長或縮小。
*   **連續記憶體：** 元素儲存在連續的記憶體位置，允許高效的隨機存取 (O(1))。
*   **高效的尾部插入/刪除：** 在尾部新增/移除元素是高效的 (攤銷 O(1))。
*   **低效的中間插入/刪除：** 在中間插入/刪除需要移動元素 (O(n))。

<UniversalEditor title="Vector vs. JavaScript Array" compare={true}>
```javascript !! js
// JavaScript: 陣列
let numbers = [1, 2, 3];
numbers.push(4); // 新增到尾部
console.log(numbers); // [1, 2, 3, 4]
console.log(numbers[1]); // 2 (隨機存取)
numbers.splice(1, 0, 99); // 在中間插入
console.log(numbers); // [1, 99, 2, 3, 4]
```

```cpp !! cpp
// C++: std::vector
#include <iostream>
#include <vector>

int main() {
  std::vector<int> numbers = {1, 2, 3};
  numbers.push_back(4); // 新增到尾部
  // std::cout << "Vector: ";
  // for (int n : numbers) { std::cout << n << " "; }
  // std::cout << std::endl;

  // std::cout << "Element at index 1: " << numbers[1] << std::endl; // 2 (隨機存取)

  numbers.insert(numbers.begin() + 1, 99); // 在中間插入
  // std::cout << "Vector after insert: ";
  // for (int n : numbers) { std::cout << n << " "; }
  // std::cout << std::endl;

  return 0;
}
```
</UniversalEditor>

### `std::list`

*   **雙向鏈結串列：** 元素不連續儲存。每個元素儲存指向前一個和後一個元素的指標。
*   **高效的任意位置插入/刪除：** 在列表中的任何位置新增/移除元素是高效的 (O(1))，一旦找到位置。
*   **低效的隨機存取：** 透過索引存取元素需要遍歷列表 (O(n))。

### `std::deque` (雙端佇列)

*   **區塊的動態陣列：** 將元素儲存在非連續的記憶體區塊中。
*   **高效的頭部/尾部插入/刪除：** 在兩端新增/移除元素是高效的 (攤銷 O(1))。
*   **高效的隨機存取：** 支援隨機存取 (O(1))，儘管比 `std::vector` 稍慢。

## 關聯容器：`map`、`set`、`unordered_map`

關聯容器以排序或雜湊方式儲存元素，允許根據鍵高效地查找。

### `std::map`

*   **排序的鍵值對：** 以鍵值對的形式儲存元素，按鍵排序。
*   **唯一鍵：** 每個鍵必須是唯一的。
*   **對數時間複雜度：** 查找、插入和刪除操作通常是 O(log n)，因為其底層是樹狀結構（通常是紅黑樹）。

<UniversalEditor title="Map vs. JavaScript Object" compare={true}>
```javascript !! js
// JavaScript: 物件 (用作雜湊映射)
let userAges = {
  "Alice": 30,
  "Bob": 25
};
userAges["Charlie"] = 35; // 新增/更新
console.log(userAges["Alice"]); // 存取
console.log("Bob" in userAges); // 檢查是否存在
delete userAges["Bob"]; // 刪除
```

```cpp !! cpp
// C++: std::map
#include <iostream>
#include <map>
#include <string>

int main() {
  std::map<std::string, int> userAges;
  userAges["Alice"] = 30;
  userAges["Bob"] = 25;
  userAges["Charlie"] = 35; // 新增/更新

  // std::cout << "Alice's age: " << userAges["Alice"] << std::endl; // 存取

  // 檢查是否存在
  // if (userAges.count("Bob")) {
  //   std::cout << "Bob exists." << std::endl;
  // }

  userAges.erase("Bob"); // 刪除

  return 0;
}
```
</UniversalEditor>

### `std::set`

*   **排序的唯一元素：** 以排序順序儲存唯一元素。
*   **對數時間複雜度：** 查找、插入和刪除是 O(log n)。

### `std::unordered_map`

*   **雜湊的鍵值對：** 使用雜湊表儲存鍵值對。
*   **唯一鍵：** 每個鍵必須是唯一的。
*   **平均常數時間複雜度：** 查找、插入和刪除通常平均為 O(1)，但在最壞情況下（雜湊衝突）可能退化為 O(n)。

### `std::unordered_set`

*   **雜湊的唯一元素：** 使用雜湊表儲存唯一元素。
*   **平均常數時間複雜度：** 查找、插入和刪除通常平均為 O(1)。

## 容器適配器：`stack`、`queue`、`priority_queue`

容器適配器為底層容器提供受限介面，強制執行特定的資料存取模式。

### `std::stack`

*   **後進先出 (LIFO)：** 元素從頂部新增和移除。
*   **操作：** `push`、`pop`、`top`、`empty`、`size`。

### `std::queue`

*   **先進先出 (FIFO)：** 元素新增到尾部，從頭部移除。
*   **操作：** `push`、`pop`、`front`、`back`、`empty`、`size`。

### `std::priority_queue`

*   **最高優先級優先：** 元素根據其優先級（預設為最大元素）檢索。
*   **操作：** `push`、`pop`、`top`、`empty`、`size`。

## 迭代器概念和用法

**迭代器**是行為類似指標的物件，允許你遍歷容器的元素。它們提供了一種通用的方式來存取元素，無論容器類型如何。

*   `begin()`：返回指向第一個元素的迭代器。
*   `end()`：返回指向最後一個元素**之後**的元素的迭代器（一個哨兵）。
*   `*iterator`：解引用迭代器以獲取元素的值。
*   `++iterator`：將迭代器移動到下一個元素。

<UniversalEditor title="迭代器用法比較" compare={true}>
```javascript !! js
// JavaScript: 使用 for...of 或 forEach 迭代
let fruits = ["apple", "banana", "cherry"];
for (let fruit of fruits) {
  console.log(fruit);
}

fruits.forEach(fruit => console.log(fruit));
```

```cpp !! cpp
// C++: 迭代器
#include <iostream>
#include <vector>
#include <string>

int main() {
  std::vector<std::string> fruits = {"apple", "banana", "cherry"};

  // 使用傳統 for 迴圈的迭代器
  // for (std::vector<std::string>::iterator it = fruits.begin(); it != fruits.end(); ++it) {
  //   std::cout << *it << std::endl;
  // }

  // 使用基於範圍的 for 迴圈 (C++11+)，它內部使用迭代器
  // for (const std::string& fruit : fruits) {
  //   std::cout << fruit << std::endl;
  // }

  return 0;
}
```
</UniversalEditor>

## 容器性能特性分析

選擇正確的容器對於性能至關重要。以下是常見操作的典型時間複雜度摘要：

| 容器         | 存取 (隨機) | 插入 (任意位置) | 刪除 (任意位置) | 搜尋 (按值) |
| :---------------- | :-------------- | :------------------- | :------------------ | :---------------- |
| `std::vector`     | O(1)            | O(n)                 | O(n)                | O(n)              |
| `std::list`       | O(n)            | O(1)                 | O(1)                | O(n)              |
| `std::deque`      | O(1)            | O(n) (中間), O(1) (兩端) | O(n) (中間), O(1) (兩端) | O(n)              |
| `std::map`        | N/A             | O(log n)             | O(log n)            | O(log n)          |
| `std::set`        | N/A             | O(log n)             | O(log n)            | O(log n)          |
| `std::unordered_map` | N/A             | O(1) (平均), O(n) (最壞) | O(1) (平均), O(n) (最壞) | O(1) (平均), O(n) (最壞) |
| `std::unordered_set` | N/A             | O(1) (平均), O(n) (最壞) | O(1) (平均), O(n) (最壞) | O(1) (平均), O(n) (最壞) |

## 與 JavaScript 陣列/物件的比較

JavaScript 的 `Array` 和 `Object` 類型功能非常強大，但它們抽象了底層的記憶體管理和特定的資料結構。C++ STL 容器提供了明確的選擇，允許開發人員為其特定需求選擇最高效的資料結構。

*   **JavaScript `Array`：** 對於數值索引，其行為有點像 `std::vector`，但也可以作為字串鍵的雜湊映射。它是一個單一、靈活的資料結構。
*   **JavaScript `Object`：** 主要是一個雜湊映射（鍵值儲存），功能類似於 `std::unordered_map` 或 `std::map`，但沒有 C++ 容器明確的性能保證或類型安全。

## 容器選擇指南

*   **`std::vector`：** 序列的預設選擇。當你需要快速隨機存取和高效的尾部新增/刪除時使用。避免頻繁地在中間插入/刪除。
*   **`std::list`：** 當你需要頻繁地在序列中的任何位置插入/刪除，並且隨機存取不是主要考量時使用。
*   **`std::deque`：** 當你需要高效地在兩端插入/刪除，並且也需要快速隨機存取時使用。
*   **`std::map` / `std::set`：** 當你需要排序的鍵值對 (map) 或唯一的排序元素 (set) 以及操作的對數時間複雜度時使用。當順序很重要時很有用。
*   **`std::unordered_map` / `std::unordered_set`：** 當你需要平均情況下 O(1) 的快速查找、插入和刪除，並且元素順序不重要時使用。雜湊表類行為的理想選擇。
*   **`std::stack` / `std::queue` / `std::priority_queue`：** 當你需要特定的 LIFO、FIFO 或基於優先級的存取模式時分別使用。

---

### 練習題：
1.  描述 `std::vector` 和 `std::list` 在其底層資料結構以及插入/刪除和隨機存取的性能特性方面的主要差異。
2.  何時會選擇 `std::map` 而不是 `std::unordered_map`，反之亦然？解釋其權衡。
3.  迭代器如何簡化 C++ 中不同 STL 容器的使用？提供一個使用迭代器遍歷 `std::vector` 和 `std::list` 的簡單範例。

### 專案構想：
*   使用 `std::map` 實作一個簡單的聯絡人管理系統，其中鍵是聯絡人的姓名（字串），值是包含其電話號碼和電子郵件的結構/類別。允許使用者新增、刪除、搜尋和顯示聯絡人。然後，嘗試使用 `std::vector` 的結構實作相同的系統，並比較搜尋操作的複雜度。
